package second;

import java.util.Scanner;

public class OsManager {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int order;//用于控制算法的使用
        int way;//用于控制方法的使用
        //进程的页面走向
        int[] datas={7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1,7, 0, 1};
        //分配主存的块数
        System.out.print("请输入分配主存的块数:");
        int length = input.nextInt();//length表示主存的块数
        System.out.print("输入1使用FIFO算法,输入2使用LRU算法,输入order:");
        order=input.nextInt();
        System.out.print("输入1使用方法1,输入2使用方法2,输入way:");
        way=input.nextInt();
        int[] memory = new int[length];
        for(int i=0;i<memory.length;i++)
            memory[i]=-1;//将数组中的值设为-1

        /*ChangeOfMemory(memory,datas[0]);
        ChangeOfMemory(memory,datas[1]);
        ChangeOfMemory(memory,datas[2]);
        ChangeOfMemory(memory,datas[3]);
        for (int i = 0; i < memory.length; i++)
            System.out.print(memory[i]+" ");*/ //测试ChangeOfMemory(int[] memory,int data)函数
        DataShow(memory, datas, order, way);
    }

    //FIFO算法,用mod方法改变主存中的数据
    public static int ChangeOfMemory_FIFO1(int[] memory,int data,int m,int k){
        k=(k+1) % m;
        memory[k]=data;
        return k;
    }
    //FIFO算法,用寄存器压栈的方法改变主存中的数据
    public static void ChangeOfMemory_FIFO2(int[] memory,int data){
        int length=memory.length;//数组memory的长度
        for(int i=length-1;i>0;i--)
            memory[i]=memory[i-1];
        memory[0]=data;
    }

    //LRU算法,使用计数器法
    public static void ChangeOfMemory_LRU1(int[] memory,int data,int[] Count){
        int length = memory.length;//数组memory的长度
        for (int i = 0; i < length; i++) {
            if (memory[i] >= 0)
                Count[i]++;
        }
        int size=get_size(memory,data,Count);
        memory[size] = data;
        Count[size] = 0;
    }
    //LRU算法,每当进程访问页面时，便将该页面的页号从栈中移出，将它压入栈顶
    public static void ChangeOfMemory_LRU2(int[] memory,int data){
        int length=memory.length;//数组memory的长度
        //使用get_connected()函数的堆栈法
        int length_tmp=get_connected(memory, data);
        for (int i = length_tmp; i > 0; i--)
            memory[i] = memory[i - 1];
        memory[0] = data;
        //不使用get_connected()函数的堆栈法
        /*int length_tmp=length-1;
        for(int i=0;i<length;i++) {
            if (memory[i] == data)
            {
                length_tmp = i;
                break;
            }
        }
        for (int j = length_tmp; j> 0; j--)
            memory[j] = memory[j - 1];
        memory[0] = data;*/

    }
    //用于LRU算法的方法1中,找到淘汰的页面
    public static int get_size(int[] memory, int data, int[] Count) {
        int length = memory.length;//数组memory的长度
        for (int i = 0; i < length; i++)
            if (memory[i] < 0)
                return i;
        int size=0;
        int num = Count[0];
        if (ls_connected(memory, data)) {
            for (int i = 0; i < length; i++) {
                if (Count[i] > num) {
                    num = Count[i];
                    size = i;
                }
            }
            return size;
        }
        else {
            for (int i = 0; i < length; i++)
                if (memory[i] == data)
                    return i;
        }
        return 0;
    }

    //用于LRU算法的方法2中,返回未被使用的下标
    public static int get_connected(int[] memory,int data){
        int length=memory.length;//数组memory的长度
        for(int i=0;i<length;i++)
            if(memory[i]==data)
                return i;
        return length-1;
    }

    //判断是否缺页，若缺页则返回true
    public static boolean ls_connected(int[] memory,int data){
        int length=memory.length;//数组memory的长度
        for(int i=0;i<length;i++)
            if(memory[i]==data)
                return false;
        return true;
    }

    //数据展示
    public static void DataShow(int[] memory,int[] datas,int order,int way){
        System.out.println("数据变化情况:");
        int length=memory.length;//数组memory的长度
        int length_sum=datas.length;//数组datas的长度,也是页面的总数
        int count=0;//记录缺页的数量
        int[] Count = new int[length];//计数器
        for(int i=0;i<length;i++)
            Count[i]=0;
        int k=0;//记录替换指针的值
        for(int i=0;i<length_sum;i++) {
            if (ls_connected(memory,datas[i])) {
                count++;
                if(order==1 && way ==1) {
                    k=ChangeOfMemory_FIFO1(memory, datas[i], length, k);
                }
                if(order==1 && way==2)
                   ChangeOfMemory_FIFO2(memory, datas[i]);
                if (order == 2 && way == 1)
                    ChangeOfMemory_LRU1(memory, datas[i],Count);
                if(order==2 && way ==2)
                    ChangeOfMemory_LRU2(memory,datas[i]);
                for(int j=0;j<length;j++) {
                    if(memory[j]>=0)
                        System.out.print(memory[j] + " ");
                    else
                        System.out.print("  ");
                }
                System.out.print("×");
                System.out.println();
            }
            else {
                if(order==1)
                    for (int j = 0; j < length; j++)
                        System.out.print("  ");
                if (order == 2 && way == 1) {
                    ChangeOfMemory_LRU1(memory, datas[i], Count);
                    for (int j = 0; j < length; j++)
                        System.out.print(memory[j] + " ");
                }
                if(order==2 && way==2) {
                    ChangeOfMemory_LRU2(memory, datas[i]);
                    for (int j = 0; j < length; j++)
                        System.out.print(memory[j] + " ");
                }
                System.out.print("√");
                System.out.println();
            }
        }

        System.out.println("算法结束,缺页率为:"+(double)count/length_sum);
    }
}
